package pcsd.server;

import java.util.Deque;
import java.util.Random;

import pcsd.Task;

/**
 * Adds a possibility for stealing tasks.
 * 
 * @author Benjamin Ertl, Justinas Murzinas, Boyan Mihaylov
 */
public class ExtendedJobQueueServer extends SimpleJobQueueServer {

	/**
	 * Instantiates the service with a given number of workers.
	 */
	public ExtendedJobQueueServer(int numWorkers, int maxDequeSize) {
		super(numWorkers, maxDequeSize);
	}
	
	/**
	 * Wait until a worker is free and steal some tasks for it if
	 * possible.
	 * @param monitor
	 */
	public void stealWork(Monitor monitor)  {
		while (true) {
			synchronized (monitor) {
				try {
					// wait for any worker to notify for an empty queue
					monitor.wait();
					
					// steal tasks for that worker if possible
					stealWorkFor(monitor.workerNum);
				}
				catch (InterruptedException e) {
					e.printStackTrace();
				}
			}
		}
	}
	
	/**
	 * Steals a task from any pending worker and adds it to another worker.
	 * @param workerNum - the worker which gets a task.
	 */
	private void stealWorkFor(int workerNum) {
		Deque<Task>[] workerDeques = this.getWorkerQueues();
		Deque<Task> currentDeque;
		int victimNum = randomWorkerNum(workerDeques.length - 1, workerNum);
		int startNum = victimNum;
		
		// Get the first pending queue of another work after victimNum
		// and steal one task from it.
		do {
			currentDeque = workerDeques[victimNum];
			synchronized (currentDeque) {
				if (currentDeque.isEmpty()) {
					victimNum++;
					if (victimNum == workerNum) victimNum++;
					
					if (victimNum >= workerDeques.length) {
						victimNum = 0;
					}
				}
				else {
					// Get the last task from the victim and add give it
					// to this worker
					workerDeques[workerNum].push(currentDeque.pollLast());
					break;
				}
			}
		}
		while (startNum != victimNum);
	}

	/**
	 * Generates a pseudo-random worker number.
	 * @param max - the upper bound (inclusive)
	 * @param excludingNum - excluding this number
	 * @return
	 */
	private static int randomWorkerNum(int max, int excludingNum){
		Random rand = new Random();
		int index = rand.nextInt(max);
		if (index == excludingNum) {
			if (index == max) {
				index = 0;
			} 
			else {
				index++;
			}
		}
		return index;
	}
}
